package NowCoder.JavaSE.String;
import java.util.*;

/**
 * HJ65 查找两个字符串a,b中的最长公共子串
 * 中等  通过率：34.83%  时间限制：1秒  空间限制：32M
 * 知识点
 * 字符串
 * warning 校招时部分企业笔试将禁止编程题跳出页面，为提前适应，练习时请使用在线自测，而非本地IDE。
 * 描述
 * 查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。
 * 注：子串的定义：将一个字符串删去前缀和后缀（也可以不删）形成的字符串。请和“子序列”的概念分开！
 *
 * 数据范围：字符串长度 1≤length≤300
 * 进阶：时间复杂度： O( n^3 ) ，空间复杂度：O(n)
 *
 * 输入描述：
 * 输入两个字符串
 * 输出描述：
 * 返回重复出现的字符
 *
 * 示例1
 * 输入：
 * abcdefghijklmnop
 * abcsafjklmnopqrstuvw
 * 输出：
 * jklmnop
 * https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506?tpId=37&tqId=21288&ru=/exam/oj
 */
public class 查找两个字符串ab中的最长公共子串_HJ65 {
    //TODO:请重新做这一道题
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        while(sc.hasNext()){
            String str1 = sc.nextLine();
            String str2 = sc.nextLine();
            recurString(str1,str2);
        }
    }

    public static void recurString(String s1,String s2){
        String shortStr = s1.length() < s2.length() ? s1 : s2;
        String longStr = s1.length() > s2.length() ? s1 : s2;
        int shortLen = shortStr.length();
        int longLen = longStr.length();
        int maxLen = 0, start = 0;
        for(int i = 0; i < shortLen;i++) {
            // 剪枝，子串长度已经不可能超过maxLen，退出循环
            if(shortLen - i + 1 <= maxLen) {
                break;
            }
            // 左指针j，右指针k, 右指针逐渐向左逼近
            for(int j = i, k = shortLen; k > j; k--) {
                String subStr = shortStr.substring(i, k);
                if(longStr.contains(subStr) && maxLen < subStr.length()) {
                    maxLen = subStr.length();
                    start = j;
                    // 找到就立即返回
                    break;
                }
            }
        }
        System.out.println(shortStr.substring(start, start + maxLen));
    }
}
